| 关于算法：如何旋转二维数组？ | 您所在的位置：网站首页 › 二维数组旋转 java › 关于算法：如何旋转二维数组？ |
|
受RaymondChen文章的启发，假设你有一个4x4二维数组，写一个旋转90度的函数。Raymond用伪代码链接到一个解决方案，但我想看看现实世界中的一些东西。 1234[1][2][3][4] [5][6][7][8] [9][0][1][2] [3][4][5][6]变成： 1234[3][9][5][1] [4][0][6][2] [5][1][7][3] [6][2][8][4]更新：尼克的回答是最直接的，但是有没有比N^2更好的方法？如果矩阵是10000x1000呢？ 相关讨论 你怎么可能不到n^2就逃走？必须读取和设置所有元素，并且有n^2个元素 另请参见stackoverflow.com/questions/848025/rotating-bitmaps-in-code 问这个问题的目的(在雷蒙德的故事中)只是为了确保候选人有一定的底线能力。n^2的解决方案很好。 你的N是什么？你不会说二维数组是方形的(一般情况下不是这样的)。例如，一个向量是一个一维为1的矩阵)，但您似乎暗示n是宽度和高度，因此具有n&178；个元素。如果n是元素数，n=w&215；h，则更合理。 与尼克萨尔达成一致。仅仅因为n恰好与某个其他值的平方强相关，就不能得到解n^2。 我没有时间写下来，但执行旋转的首选方法是使用四元数。 如果它的维度是NxM，而不是NxN，则更具挑战性。 请注意，对于大型数组，缓存未命中可能是有问题的，因此您需要按照stackoverflow.com/questions/848025/rotating-bitmaps-in-code的答案中的建议使用tiling。这样，您将得到一个四嵌套循环。 这是一种快速的方法：存储行和列索引(比如I和J)。转置需要恒定的时间(只需交换索引：)。您可以对旋转进行同样的操作(使用索引)。 如果n^2不可行。您可以创建一个访问每个元素的接口。然后给定(i，j)，将旋转应用于(i，j)访问旋转的元素并返回。也许不是最好的单曲，但效果很好。 我想你还是可以在n^2以下完成。但是，需要更复杂的数据结构。也许是某种双重链接列表？ @艾瑞克艾伦，它能被压缩吗？O(N ^ 2)的时间和O(1)算法的空间(没有任何workarounds和hanky - panky东西！) 前言：rotate + 90 transpose 反对方行前言：rotate 90 方法一： transpose 反对方柱方法2： 反对方行 transpose前言：rotate + 180 方法：由一个rotate + 90次 方法2：反对方，然后反每一列(Row transpose) 前言：rotate - 180 方法1：rotate由90次 方法2：反每一列的每一行，然后反 方法三：由+ 180 rotate作为他们是相同的 相关讨论 这对我很有帮助；当我知道这个操作的[伪代码版本]时，我就能够编写一个算法。谢谢！ 我最喜欢的答案之一。很有启发性！ 这里有一个Javascript实现JSfiddle，如果有人感兴趣的话。 旋转-90：(1)每行反转；(2)换位。haskell:rotateCW = map reverse . transpose和rotateCCW = transpose . map reverse。 要旋转-90，每行反转，然后换位将比换位快，然后每列反转。缓存一致性是个大问题 对于简单的解空间不会是O(1)"就地矩阵转置"也不是那么直接，对于简单的解，你必须使用临时矩阵来存储转置的矩阵。不过，很好的解决方案！ stackoverflow.com/a/35137982/1052261 美丽的。应该注意的是，如果维度不同，O(1)空间是不可能的，因为无论必须创建另一个数组。 旋转180和-180有什么区别？ @Elgsqianchen没有。90、180、270分别对应于-270、-180、-90。因此，旋转90与旋转-270相同，以此类推。实际上，所有情况下只需要三个唯一的旋转(如果为0，则只需返回原始矩阵)。 出色的解决方案。这有点类似于一维阵列旋转——这是它的辉煌。互联网上还有其他解决方案，这一个是最好的。 我是唯一不能证明这个算法正确的人吗？：(我想再加一点细节。在这个答案中，关键概念是重复的，节奏缓慢，有意重复。然而，这里提供的解决方案在语法上并不是最紧凑的，它是为那些希望了解矩阵旋转是什么以及结果实现的人设计的。好的。 首先，什么是矩阵？在这个答案中，矩阵只是一个宽度和高度相同的网格。注意，矩阵的宽度和高度可以不同，但为了简单起见，本教程只考虑宽度和高度相等的矩阵(正方形矩阵)。是的，矩阵是矩阵的复数。好的。 示例矩阵为：2×2、3×3或5×5。或者，更一般地说，n×n。一个2×2矩阵将有4个正方形，因为2×2=4。一个5×5的矩阵将有25个正方形，因为5×5=25。每个方块都被称为元素或入口。我们将在下图中用句点(.表示每个元素：好的。 2×2矩阵好的。 12. . . .3×3矩阵好的。 123. . . . . . . . .4×4矩阵好的。2 那么，旋转矩阵意味着什么呢？让我们取一个2×2的矩阵，在每个元素中加上一些数字，这样就可以观察到旋转：好的。 120 1 2 3旋转90度可以得到：好的。 122 0 3 1我们真的把整个矩阵向右转了一次，就像转动汽车的方向盘一样。这可能有助于思考"倾斜"矩阵的右边。我们想用python编写一个函数，它接受一个矩阵并向右旋转一次。函数签名将是：好的。 12def rotate(matrix): # Algorithm goes here.矩阵将使用二维数组定义：好的。 1234matrix = [ [0,1], [2,3] ]因此，第一个索引位置访问行。第二个索引位置访问列：好的。 1matrix[row][column]我们将定义一个实用函数来打印矩阵。好的。 123def print_matrix(matrix): for row in matrix: print row旋转矩阵的一种方法是一次旋转一层。但是什么是层呢？想想洋葱。就像洋葱的每一层，当每一层被移除时，我们都会向中心移动。其他的类比是一个套娃或一个传递包裹的游戏。好的。 矩阵的宽度和高度决定了该矩阵中的层数。让我们为每一层使用不同的符号：好的。 2×2矩阵有1层好的。 12. . . .3×3矩阵有两层好的。 123. . . . x . . . .4×4矩阵有两层好的。 1234. . . . . x x . . x x . . . . .5×5矩阵有3层好的。 12345. . . . . . x x x . . x O x . . x x x . . . . . .6×6矩阵有3层好的。 123456. . . . . . . x x x x . . x O O x . . x O O x . . x x x x . . . . . . .7×7矩阵有4层好的。 1234567. . . . . . . . x x x x x . . x O O O x . . x O - O x . . x O O O x . . x x x x x . . . . . . . .您可能会注意到，将矩阵的宽度和高度增加一，并不总是增加层的数量。采用上述矩阵，并将各层和尺寸制成表格，我们发现每增加两个宽度和高度，各层的数量就会增加一次：好的。 1234567891011+-----+--------+ | N×N | Layers | +-----+--------+ | 1×1 | 1 | | 2×2 | 1 | | 3×3 | 2 | | 4×4 | 2 | | 5×5 | 3 | | 6×6 | 3 | | 7×7 | 4 | +-----+--------+然而，并非所有层都需要旋转。1×1矩阵在旋转前后是相同的。中心1×1层在旋转前后始终相同，无论整体矩阵有多大：好的。 1234567891011+-----+--------+------------------+ | N×N | Layers | Rotatable Layers | +-----+--------+------------------+ | 1×1 | 1 | 0 | | 2×2 | 1 | 1 | | 3×3 | 2 | 1 | | 4×4 | 2 | 2 | | 5×5 | 3 | 2 | | 6×6 | 3 | 3 | | 7×7 | 4 | 3 | +-----+--------+------------------+给定n×n矩阵，我们如何以编程方式确定需要旋转的层数？如果我们将宽度或高度除以2，忽略余数，我们得到以下结果。好的。2 注意，N/2如何匹配需要旋转的层数？有时，可旋转层的数量比矩阵中的总层数少一个。当最内层仅由一个元素(即1×1矩阵)构成，因此不需要旋转时，就会发生这种情况。它只是被忽略了。好的。 毫无疑问，我们在函数中需要这些信息来旋转矩阵，现在让我们添加它：好的。 1234def rotate(matrix): size = len(matrix) # Rotatable layers only. layer_count = size / 2现在我们知道了什么是层，以及如何确定实际需要旋转的层的数量，我们如何隔离一个层以便旋转它？首先，我们检查从最外层到最内层的矩阵。5×5矩阵共有三层，需要旋转的两层：好的。 12345. . . . . . x x x . . x O x . . x x x . . . . . .让我们先看看列。定义最外层的列的位置(假设我们从0开始计数)是0和4：好的。 123456789+--------+-----------+ | Column | 0 1 2 3 4 | +--------+-----------+ | | . . . . . | | | . x x x . | | | . x O x . | | | . x x x . | | | . . . . . | +--------+-----------+0和4也是最外层行的位置。好的。 123456789+-----+-----------+ | Row | | +-----+-----------+ | 0 | . . . . . | | 1 | . x x x . | | 2 | . x O x . | | 3 | . x x x . | | 4 | . . . . . | +-----+-----------+因为宽度和高度是相同的，所以情况总是如此。因此，我们可以定义只有两个值(而不是四个)的层的列和行位置。好的。 向内移动到第二层，列的位置是1和3。是的，你猜对了，行也是一样的。重要的是要理解，当向内移动到下一层时，我们必须同时增加和减少行和列的位置。好的。 1234567+-----------+---------+---------+---------+ | Layer | Rows | Columns | Rotate? | +-----------+---------+---------+---------+ | Outermost | 0 and 4 | 0 and 4 | Yes | | Inner | 1 and 3 | 1 and 3 | Yes | | Innermost | 2 | 2 | No | +-----------+---------+---------+---------+因此，为了检查每一层，我们需要一个循环，从最外层开始，循环中包含表示向内移动的递增和递减计数器。我们称之为"层循环"。好的。 12345678910111213141516171819def rotate(matrix): size = len(matrix) layer_count = size / 2 for layer in range(0, layer_count): first = layer last = size - first - 1 print 'Layer %d: first: %d, last: %d' % (layer, first, last) # 5x5 matrix matrix = [ [ 0, 1, 2, 3, 4], [ 5, 6, 6, 8, 9], [10,11,12,13,14], [15,16,17,18,19], [20,21,22,23,24] ] rotate(matrix)上面的代码循环通过需要旋转的任何层的(行和列)位置。好的。 12Layer 0: first: 0, last: 4 Layer 1: first: 1, last: 3我们现在有一个循环，提供每层的行和列的位置。变量first和last标识第一行和最后一行和最后一列的索引位置。返回行和列表：好的。 12345678910111213141516171819+--------+-----------+ | Column | 0 1 2 3 4 | +--------+-----------+ | | . . . . . | | | . x x x . | | | . x O x . | | | . x x x . | | | . . . . . | +--------+-----------+ +-----+-----------+ | Row | | +-----+-----------+ | 0 | . . . . . | | 1 | . x x x . | | 2 | . x O x . | | 3 | . x x x . | | 4 | . . . . . | +-----+-----------+所以我们可以在矩阵的各个层中导航。现在我们需要一种在层中导航的方法，这样我们就可以在该层周围移动元素。注意，元素从不从一个层跳到另一个层，但它们确实在各自的层中移动。好的。 旋转层中的每个元素将旋转整个层。旋转矩阵中的所有层可以旋转整个矩阵。这句话很重要，所以请在继续之前尽力理解它。好的。 现在，我们需要一种实际移动元素的方法，即旋转每个元素，然后旋转层，最后旋转矩阵。为了简单起见，我们将恢复到一个3x3矩阵-它有一个可旋转层。好的。 1230 1 2 3 4 5 6 7 8我们的层循环提供第一列和最后一列以及第一行和最后一行的索引：好的。 123456789101112131415+-----+-------+ | Col | 0 1 2 | +-----+-------+ | | 0 1 2 | | | 3 4 5 | | | 6 7 8 | +-----+-------+ +-----+-------+ | Row | | +-----+-------+ | 0 | 0 1 2 | | 1 | 3 4 5 | | 2 | 6 7 8 | +-----+-------+因为我们的矩阵总是正方形的，所以我们只需要两个变量，即first和last，因为行和列的索引位置是相同的。好的。2 第一个和最后一个变量可以很容易地用来引用矩阵的四个角。这是因为角本身可以使用first和last的各种排列来定义(这些变量没有减法、加法或偏移)：好的。 12345678+---------------+-------------------+-------------+ | Corner | Position | 3x3 Values | +---------------+-------------------+-------------+ | top left | (first, first) | (0,0) | | top right | (first, last) | (0,2) | | bottom right | (last, last) | (2,2) | | bottom left | (last, first) | (2,0) | +---------------+-------------------+-------------+因为这个原因，我们从外面的四个角开始旋转，我们先旋转它们。让我们用*来突出它们。好的。 123* 1 * 3 4 5 * 7 *我们想把每个*和*互换到它的右边。因此，让我们继续打印我们的角点，只使用first和last的各种排列：好的。 12345678910111213141516171819202122232425def rotate(matrix): size = len(matrix) layer_count = size / 2 for layer in range(0, layer_count): first = layer last = size - first - 1 top_left = (first, first) top_right = (first, last) bottom_right = (last, last) bottom_left = (last, first) print 'top_left: %s' % (top_left) print 'top_right: %s' % (top_right) print 'bottom_right: %s' % (bottom_right) print 'bottom_left: %s' % (bottom_left) matrix = [ [0, 1, 2], [3, 4, 5], [6, 7, 8] ] rotate(matrix)输出应为：好的。 1234top_left: (0, 0) top_right: (0, 2) bottom_right: (2, 2) bottom_left: (2, 0)现在，我们可以很容易地从层循环中交换每个角：好的。 123456789101112131415161718192021222324252627def rotate(matrix): size = len(matrix) layer_count = size / 2 for layer in range(0, layer_count): first = layer last = size - first - 1 top_left = matrix[first][first] top_right = matrix[first][last] bottom_right = matrix[last][last] bottom_left = matrix[last][first] # bottom_left -> top_left matrix[first][first] = bottom_left # top_left -> top_right matrix[first][last] = top_left # top_right -> bottom_right matrix[last][last] = top_right # bottom_right -> bottom_left matrix[last][first] = bottom_right print_matrix(matrix) print '---------' rotate(matrix) print_matrix(matrix)转角前矩阵：好的。 123[0, 1, 2] [3, 4, 5] [6, 7, 8]转角后的矩阵：好的。 123[6, 1, 0] [3, 4, 5] [8, 7, 2]伟大的！我们已经成功地旋转了矩阵的每个角。但是，我们没有旋转每层中间的元素。显然，我们需要一种在层内迭代的方法。好的。 问题是，到目前为止，函数中唯一的循环(我们的层循环)在每次迭代中移动到下一层。因为我们的矩阵只有一个可旋转层，所以层循环在只旋转角之后退出。让我们看一个更大的5×5矩阵会发生什么(两个层需要旋转)。功能代码已被省略，但仍与上面相同：好的。 1234567891011matrix = [ [0, 1, 2, 3, 4], [5, 6, 7, 8, 9], [10, 11, 12, 13, 14], [15, 16, 17, 18, 19], [20, 21, 22, 23, 24] ] print_matrix(matrix) print '--------------------' rotate(matrix) print_matrix(matrix)输出是：好的。 12345[20, 1, 2, 3, 0] [ 5, 16, 7, 6, 9] [10, 11, 12, 13, 14] [15, 18, 17, 8, 19] [24, 21, 22, 23, 4]最外层的角已经旋转了，这并不奇怪，但是您可能也注意到下一层的角(向内)也已经旋转了。这是有道理的。我们已经编写了代码来浏览各个层，还可以旋转每个层的角。这感觉像是进步，但不幸的是我们必须后退一步。在上一(外部)层完全旋转之前，移动到下一层是不好的。也就是说，直到层中的每个元素都被旋转。只旋转转角是不行的！好的。 深呼吸。我们需要另一个循环。一个嵌套的循环。新的嵌套循环将使用first和last变量，加上偏移量在层内导航。我们将这个新循环称为"元素循环"。元素循环将沿着顶行访问每个元素，每一个元素位于右侧，每一个元素位于底行，每一个元素位于左侧。好的。 沿顶行向前移动需要列要递增的索引。 向下移动右侧需要行索引为递增。 沿底部向后移动需要柱要递减的索引。 向上移动左侧需要行索引为递减的这听起来很复杂，但这很容易，因为我们为实现上述目标而增加和减少的次数在矩阵的所有四个边上都保持不变。例如：好的。 将1个元素移过顶行。 将一个元素向下移动到右侧。 沿底行向后移动1个元素。 将1个元素向上移动到左侧。这意味着我们可以将单个变量与first和last变量结合使用，在一个层中移动。需要注意的是，在最上面一行和最右边移动都需要递增。沿底部和左侧向后移动时，两者都需要减量。好的。 12345678910111213141516171819202122232425262728def rotate(matrix): size = len(matrix) layer_count = size / 2 # Move through layers (i.e. layer loop). for layer in range(0, layer_count): first = layer last = size - first - 1 # Move within a single layer (i.e. element loop). for element in range(first, last): offset = element - first # 'element' increments column (across right) top_element = (first, element) # 'element' increments row (move down) right_side = (element, last) # 'last-offset' decrements column (across left) bottom = (last, last-offset) # 'last-offset' decrements row (move up) left_side = (last-offset, first) print 'top: %s' % (top) print 'right_side: %s' % (right_side) print 'bottom: %s' % (bottom) print 'left_side: %s' % (left_side)现在我们只需要将顶部分配给右侧，右侧分配给底部，底部分配给左侧，左侧分配给顶部。把这些放在一起，我们得到：好的。 1234567891011121314151617181920def rotate(matrix): size = len(matrix) layer_count = size / 2 for layer in range(0, layer_count): first = layer last = size - first - 1 for element in range(first, last): offset = element - first top = matrix[first][element] right_side = matrix[element][last] bottom = matrix[last][last-offset] left_side = matrix[last-offset][first] matrix[first][element] = left_side matrix[element][last] = top matrix[last][last-offset] = right_side matrix[last-offset][first] = bottom给定矩阵：好的。2 我们的rotate功能导致：好的。 1236, 3, 0 7, 4, 1 8, 5, 2好啊。 相关讨论 最好的解释。如果有一个捐赠按钮，我会很乐意为您的详细答复捐赠10美元。非常感谢你 了解将矩阵旋转90度的整个概念。非常感谢你如此详细的解释。 @坎特芬达纳梅88，但你本可以赏金的… 惊人的解释。我刚刚学会了矩阵，如果可能的话，我会把它放在我的阅读列表中！ 这也教会了我，如何深入研究这个问题并从中找出逻辑。 对这个算法最好的解释！干得好，杰克！ 起初我觉得"哇，有史以来最好的解释"，但在读了几遍之后(为了确保我不会错过任何重要的字里行间)，我的观点变为"伙计，我明白了，我们能继续前进吗？"对于花几个小时来写出如此详尽的答案，人们仍持反对意见。 @Abhijitsarkar——谢谢你的投票，我希望它至少在一些小的方面有所帮助。当然，你是对的，我的回答很冗长。然而，这与大多数答案形成了鲜明的对比。正如我在回答开始时所说："在这个答案中，关键的概念是重复的，速度是缓慢的，有意重复的。"如果你有保持清晰和必要的重复性的编辑，但减少了字数，我很愿意接受建议。或者只是编辑： @杰克解释得很好。但是，我无法理解，你是怎么想到offset=element-first和last=size-first-1的？很难理解？另外，最后一个偏移量与偏移量相同吗？这是C的# 1234567891011121314151617181920int[,] array = new int[4,4] { { 1,2,3,4 }, { 5,6,7,8 }, { 9,0,1,2 }, { 3,4,5,6 } }; int[,] rotated = RotateMatrix(array, 4); static int[,] RotateMatrix(int[,] matrix, int n) { int[,] ret = new int[n, n]; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { ret[i, j] = matrix[n - j - 1, i]; } } return ret; } 相关讨论 当然，但是使用O(1)内存的解决方案呢？ 您的解决方案具有O(n^2)空间复杂性。需要做得更好 对于n x m矩阵呢？ 复杂度与数组中的元素数呈线性关系。如果n是元素的数量，那么复杂性是o(n)。如果n是边的长度，那么是的，复杂度是o(n^2)，但这仍然是最佳的。你必须至少读一次每一个元素。打印矩阵同样复杂 只有当矩阵是正方形时，它才起作用。 这里添加了一个N x m矩阵的答案：stackoverflow.com/a/38027015/1322703 @kshitijjain空间复杂性如何？他正在复制数组，所以它不是O(N)空间吗？ 对于-90度旋转：ret[i][j] = matrix[j][n - i - 1]。 如果我错了，请纠正我，但是并行性(前提是系统有合理数量的内核)不能降低复杂性，即使只是稍微降低一点？Python： 1rotated = zip(*original[::-1]) # On Python 3, list(zip(*original[::-1]))廉价的，我知道。 和counterclockwise： 1rotated_ccw = zip(*original)[::-1] # On Python 3, list(zip(*original))[::-1]如何：(设计了这个作品在评论) zip(*original)威尔swap axes的二维arrays由从对应的stacking items列出成新的列表。(《*告诉操作员的功能distribute列出其中的成大的支持) 12>>> zip(*[[1,2,3],[4,5,6],[7,8,9]]) [[1,4,7],[2,5,8],[3,6,9]]该项声明[::-1]reverses阵列元素(请参见扩展slices)。 12>>> [[1,2,3],[4,5,6],[7,8,9]][::-1] [[7,8,9],[4,5,6],[1,2,3]]最后，将导致在两combining旋转转型。 的位置的变化在[::-1]将列出在不同水平的反矩阵。 相关讨论 我相信这段代码源于peter norvig:norvig.com/python-iaq.html 是否有一个简单的方法来逆时针旋转使用这个，而不是运行它三次？ @杏仁核：是的，我也包括了它的代码。 和鲁比一样，但还有26票，嗯…啊，没看回答时间戳。 除了这个很好的答案，我还想得到一个解释。(拉链让我头晕目眩) rotated_ccw = zip(*original)[::-1]还是rotated_ccw = list(zip(*original))[::-1]？第一个给了我错误。在Windows上使用python 3.3。 它是为python 2设计的。这是一个在适当位置执行旋转的方法，而不是使用一个全新的数组来保存结果。我已经停止了数组的初始化并将其打印出来。这只适用于方形阵列，但它们可以是任何大小。内存开销等于数组中一个元素的大小，因此可以根据需要旋转任意大的数组。 1234567891011121314int a[4][4]; int n = 4; int tmp; for (int i = 0; i < n / 2; i++) { for (int j = i; j < n - i - 1; j++) { tmp = a[i][j]; a[i][j] = a[j][n-i-1]; a[j][n-i-1] = a[n-i-1][n-j-1]; a[n-i-1][n-j-1] = a[n-j-1][i]; a[n-j-1][i] = tmp; } } 相关讨论 我至少能看到一只虫子。如果你要发布代码，测试它，或者至少说你还没有这样做。 哪里？把它指出来，我会修好的。我做了测试，它在奇数和偶数大小的数组上都能很好地工作。 仅仅从观察：第二个循环开始测试j 你说得对。真奇怪。我相信应该有一个N在那里，当我张贴它时我遗漏了。在列表中修复了它。 这是一个很好的解决方案。如果有目的的话，头脑可以完成这样的壮举。从O(n2)到O(1) 不是O(1)；还是O(n^2) 它的O(n^2)和内存O(1)。 我真的链接了你划分数组的方式：) 应用这一点的关键是"到位"； 记住，这只是逆时针旋转——也许顺时针旋转是留给学生的一个练习？；) 以下链接geeksforgeks.org/inplace-rotate-square-matrix-by-90度也提到了类似的解决方案。这里有很多好的代码，但我只是想从几何角度展示正在发生的事情，这样您就可以更好地理解代码逻辑。下面是我将如何处理这个问题。 首先，不要把这个和换位混淆，这很容易。 basica的想法是把它当作层来处理，我们一次旋转一层。 假设我们有4x4 12341 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16当我们顺时针旋转90度后，我们得到 123413 9 5 1 14 10 6 2 15 11 7 3 16 12 8 4让我们来分解这个，首先我们基本上旋转4个角 2然后我们旋转下面的钻石，它有点歪斜 1234 2 8 9 15然后是第二颗歪斜的钻石 1234 3 5 12 14所以这要考虑到外缘，所以我们一次只做一个壳，直到 最后是中间的正方形(或者如果它是奇数，则是不移动的最后一个元素) 126 7 10 11现在让我们计算出每一层的索引，假设我们总是使用最外层，我们正在这样做 123[0,0] -> [0,n-1], [0,n-1] -> [n-1,n-1], [n-1,n-1] -> [n-1,0], and [n-1,0] -> [0,0] [0,1] -> [1,n-1], [1,n-2] -> [n-1,n-2], [n-1,n-2] -> [n-2,0], and [n-2,0] -> [0,1] [0,2] -> [2,n-2], [2,n-2] -> [n-1,n-3], [n-1,n-3] -> [n-3,0], and [n-3,0] -> [0,2]如此等等直到我们走到边缘的一半 一般来说，模式是 1[0,i] -> [i,n-i], [i,n-i] -> [n-1,n-(i+1)], [n-1,n-(i+1)] -> [n-(i+1),0], and [n-(i+1),0] to [0,i] 相关讨论 "半途而废"是什么意思？我看到很多算法循环直到n/2，其他算法循环到n，但我看不到n/2的来源。 我相信这和破解编码面试的方法是一样的。但我喜欢循序渐进的解释。很好，很彻底。 @PDN这个答案详细解释了它。正如我在上一篇文章中所说，这里有一些C中的代码，它实现了任何大小矩阵的O(1)矩阵旋转。为了简洁易读，没有错误检查或范围检查。代码： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170static void Main (string [] args) { int [,] // create an arbitrary matrix m = {{0, 1}, {2, 3}, {4, 5}}; Matrix // create wrappers for the data m1 = new Matrix (m), m2 = new Matrix (m), m3 = new Matrix (m); // rotate the matricies in various ways - all are O(1) m1.RotateClockwise90 (); m2.Rotate180 (); m3.RotateAnitclockwise90 (); // output the result of transforms System.Diagnostics.Trace.WriteLine (m1.ToString ()); System.Diagnostics.Trace.WriteLine (m2.ToString ()); System.Diagnostics.Trace.WriteLine (m3.ToString ()); } class Matrix { enum Rotation { None, Clockwise90, Clockwise180, Clockwise270 } public Matrix (int [,] matrix) { m_matrix = matrix; m_rotation = Rotation.None; } // the transformation routines public void RotateClockwise90 () { m_rotation = (Rotation) (((int) m_rotation + 1) & 3); } public void Rotate180 () { m_rotation = (Rotation) (((int) m_rotation + 2) & 3); } public void RotateAnitclockwise90 () { m_rotation = (Rotation) (((int) m_rotation + 3) & 3); } // accessor property to make class look like a two dimensional array public int this [int row, int column] { get { int value = 0; switch (m_rotation) { case Rotation.None: value = m_matrix [row, column]; break; case Rotation.Clockwise90: value = m_matrix [m_matrix.GetUpperBound (0) - column, row]; break; case Rotation.Clockwise180: value = m_matrix [m_matrix.GetUpperBound (0) - row, m_matrix.GetUpperBound (1) - column]; break; case Rotation.Clockwise270: value = m_matrix [column, m_matrix.GetUpperBound (1) - row]; break; } return value; } set { switch (m_rotation) { case Rotation.None: m_matrix [row, column] = value; break; case Rotation.Clockwise90: m_matrix [m_matrix.GetUpperBound (0) - column, row] = value; break; case Rotation.Clockwise180: m_matrix [m_matrix.GetUpperBound (0) - row, m_matrix.GetUpperBound (1) - column] = value; break; case Rotation.Clockwise270: m_matrix [column, m_matrix.GetUpperBound (1) - row] = value; break; } } } // creates a string with the matrix values public override string ToString () { int num_rows = 0, num_columns = 0; switch (m_rotation) { case Rotation.None: case Rotation.Clockwise180: num_rows = m_matrix.GetUpperBound (0); num_columns = m_matrix.GetUpperBound (1); break; case Rotation.Clockwise90: case Rotation.Clockwise270: num_rows = m_matrix.GetUpperBound (1); num_columns = m_matrix.GetUpperBound (0); break; } StringBuilder output = new StringBuilder (); output.Append ("{"); for (int row = 0 ; row newarr.push(new Array(arr.length))); for (var i = 0; i < newarr[0].length; i++) { for (var j = 0; j < newarr.length; j++) { newarr[j][i] = getArray2dCW(arr, i, j); } } console.log(newarr);2 12345678910111213141516171819202122232425// Get an array element rotated 180 degrees function getArray2d180(a, x, y) { x = a[0].length - x - 1; y = a.length - y - 1; return a[y][x]; } //demo var arr = [ [5, 4, 6], [1, 7, 9], [-2, 11, 0], [8, 21, -3], [3, -1, 2] ]; var newarr = []; arr.forEach(() => newarr.push(new Array(arr[0].length))); for (var i = 0; i < newarr[0].length; i++) { for (var j = 0; j < newarr.length; j++) { newarr[j][i] = getArray2d180(arr, i, j); } } console.log(newarr);此代码假定嵌套数组的数组，其中每个内部数组都是一行。 该方法允许您读取(或写入)元素(甚至以随机顺序)，就像数组已被旋转或转换一样。现在只需选择正确的函数来调用，可能是通过引用来调用的，然后离开！ 这个概念可以扩展为通过访问器方法附加地(和非破坏性地)应用转换。包括任意角度旋转和缩放。 相关讨论 但这些都不是从原始数组中旋转出来的。第一个，最终的结果是简单的转置。第二个，您似乎刚刚洗牌的行或镜像跨越水平中心。第三，只颠倒了行，第四行也被转置了。没有一个是真正"旋转"的。 后两个例子中有一些错误。小事一桩。我明确指出，这个解决方案不是就地旋转。它是一个转换函数，这使得它适合于延迟迭代。 但是没有旋转，所以你没有回答手术要求。 @SM177Y另一个编辑器在我的答案中添加了不工作的示例代码。我看得出你对它有多困惑。我已经修复了迭代循环中的错误。所提供的函数实际上会"旋转"数组中的数据。 同样重要的细节是，示例代码确实冲掉了我提供的原始答案，它试图说明函数转换在线性时空复杂度解决方案上的威力。通过函数转换，您已经在迭代或以其他方式访问数组元素，因此在空间和时间复杂性不变的意义上，转换被认为是"自由的"。一些人已经举了一些例子，其中包括创建一个新的数组。 需要考虑的其他一些事项： (a)不需要实际移动数据，只需以不同的方式遍历"旋转"数组即可。 (b)在适当的位置进行旋转可能有点棘手。您将需要一些临时位置(大概相当于一行或一列的大小)。有一篇关于就地转置的古老ACM论文(http://doi.acm.org/10.1145/355719.355729)，但是他们的示例代码是讨厌的Goto-Laden Fortran。 附录： http://doi.acm.org/10.1145/355611.355612是另一种据称更优越的就地转置算法。 相关讨论 我同意这一点。具有确定源数据和"旋转"数据之间的转换的方法。Nick的答案也适用于NXM阵列，只需稍作修改(与NXN相反)。 12345678string[,] orig = new string[n, m]; string[,] rot = new string[m, n]; ... for ( int i=0; i < n; i++ ) for ( int j=0; j < m; j++ ) rot[j, n - i - 1] = orig[i, j];考虑到这一点的一种方法是将轴的中心(0,0)从左上角移动到右上角。你只是简单地从一个调换到另一个。 时间-O(N)，空间-O(1) 12345678910111213public void rotate(int[][] matrix) { int n = matrix.length; for (int i = 0; i < n / 2; i++) { int last = n - 1 - i; for (int j = i; j < last; j++) { int top = matrix[i][j]; matrix[i][j] = matrix[last - j][i]; matrix[last - j][i] = matrix[last][last - j]; matrix[last][last - j] = matrix[j][last]; matrix[j][last] = top; } } } 相关讨论 这不是O(1)。这是O(n)。 @Jasonoster我认为这是O(1)空间，因为它不消耗额外的空间。 @我犯了错误。o(1)空间复杂性，是的。o(n)时间复杂性。 空间复杂性也是O(N)。空间复杂度应包括输入变量大小的空间。careercup.com/question？ID＝14952322 我怎样才能修改它，使其逆时针旋转？这是我的Ruby版本(请注意，这些值显示的不一样，但它仍按描述旋转)。 123456789101112131415161718192021222324252627282930def rotate(matrix) result = [] 4.times { |x| result[x] = [] 4.times { |y| result[x][y] = matrix[y][3 - x] } } result end matrix = [] matrix[0] = [1,2,3,4] matrix[1] = [5,6,7,8] matrix[2] = [9,0,1,2] matrix[3] = [3,4,5,6] def print_matrix(matrix) 4.times { |y| 4.times { |x| print"#{matrix[x][y]}" } puts"" } end print_matrix(matrix) puts"" print_matrix(rotate(matrix))输出： 2这是一个在空间rotate方法，由Java，只为广场。对于非广场的二维阵列，你将要创建新阵列吧。 123456789101112131415161718private void rotateInSpace(int[][] arr) { int z = arr.length; for (int i = 0; i < z / 2; i++) { for (int j = 0; j < (z / 2 + z % 2); j++) { int x = i, y = j; int temp = arr[x][y]; for (int k = 0; k < 4; k++) { int temptemp = arr[y][z - x - 1]; arr[y][z - x - 1] = temp; temp = temptemp; int tempX = y; y = z - x - 1; x = tempX; } } } }大尺寸rotate代码由任何二维阵列创建新阵列： 1234567891011private int[][] rotate(int[][] arr) { int width = arr[0].length; int depth = arr.length; int[][] re = new int[width][depth]; for (int i = 0; i < depth; i++) { for (int j = 0; j < width; j++) { re[j][depth - i - 1] = arr[i][j]; } } return re; }您可以通过3个简单步骤来完成此操作： 1)假设我们有一个矩阵 123 1 2 3 4 5 6 7 8 92)取矩阵的转置 123 1 4 7 2 5 8 3 6 93)交换行以获得旋转矩阵 123 3 6 9 2 5 8 1 4 7Java源代码： 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253public class MyClass { public static void main(String args[]) { Demo obj = new Demo(); /*initial matrix to rotate*/ int[][] matrix = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }; int[][] transpose = new int[3][3]; // matrix to store transpose obj.display(matrix); // initial matrix obj.rotate(matrix, transpose); // call rotate method System.out.println(); obj.display(transpose); // display the rotated matix } } class Demo { public void rotate(int[][] mat, int[][] tran) { /* First take the transpose of the matrix */ for (int i = 0; i < mat.length; i++) { for (int j = 0; j < mat.length; j++) { tran[i][j] = mat[j][i]; } } /* * Interchange the rows of the transpose matrix to get rotated * matrix */ for (int i = 0, j = tran.length - 1; i != j; i++, j--) { for (int k = 0; k < tran.length; k++) { swap(i, k, j, k, tran); } } } public void swap(int a, int b, int c, int d, int[][] arr) { int temp = arr[a][b]; arr[a][b] = arr[c][d]; arr[c][d] = temp; } /* Method to display the matrix */ public void display(int[][] arr) { for (int i = 0; i < arr.length; i++) { for (int j = 0; j < arr.length; j++) { System.out.print(arr[i][j] +""); } System.out.println(); } } }输出： 12345671 2 3 4 5 6 7 8 9 3 6 9 2 5 8 1 4 7实施的dimple OH + 90 pseudocode(例如transpose在JavaScript然后反向每Row)： 123456789function rotate90(a){ // transpose from http://www.codesuck.com/2012/02/transpose-javascript-array-in-one-line.html a = Object.keys(a[0]).map(function (c) { return a.map(function (r) { return r[c]; }); }); // row reverse for (i in a){ a[i] = a[i].reverse(); } return a; }这是我的实施，C，O(1)内存的复杂性，在顺时针旋转90度的地方，： 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#include #define M_SIZE 5 static void initMatrix(); static void printMatrix(); static void rotateMatrix(); static int m[M_SIZE][M_SIZE]; int main(void){ initMatrix(); printMatrix(); rotateMatrix(); printMatrix(); return 0; } static void initMatrix(){ int i, j; for(i = 0; i < M_SIZE; i++){ for(j = 0; j < M_SIZE; j++){ m[i][j] = M_SIZE*i + j + 1; } } } static void printMatrix(){ int i, j; printf("Matrix "); for(i = 0; i < M_SIZE; i++){ for(j = 0; j < M_SIZE; j++){ printf("%02d", m[i][j]); } printf(" "); } printf(" "); } static void rotateMatrix(){ int r, c; for(r = 0; r < M_SIZE/2; r++){ for(c = r; c < M_SIZE - r - 1; c++){ int tmp = m[r][c]; m[r][c] = m[M_SIZE - c - 1][r]; m[M_SIZE - c - 1][r] = m[M_SIZE - r - 1][M_SIZE - c - 1]; m[M_SIZE - r - 1][M_SIZE - c - 1] = m[c][M_SIZE - r - 1]; m[c][M_SIZE - r - 1] = tmp; } } }PHP： 12345678910111213从线性角度来看，考虑矩阵： 123 1 2 3 0 0 1 A = 4 5 6 B = 0 1 0 7 8 9 1 0 0现在换位 123 1 4 7 A' = 2 5 8 3 6 9并考虑a'对b，或b对a'的作用。分别： 123 7 4 1 3 6 9 A'B = 8 5 2 BA' = 2 5 8 9 6 3 1 4 7这对于任何n x n矩阵都是可扩展的。在代码中快速应用这个概念： 1234567891011121314151617181920212223242526272829303132void swapInSpace(int** mat, int r1, int c1, int r2, int c2) { mat[r1][c1] ^= mat[r2][c2]; mat[r2][c2] ^= mat[r1][c1]; mat[r1][c1] ^= mat[r2][c2]; } void transpose(int** mat, int size) { for (int i = 0; i < size; i++) { for (int j = (i + 1); j < size; j++) { swapInSpace(mat, i, j, j, i); } } } void rotate(int** mat, int size) { //Get transpose transpose(mat, size); //Swap columns for (int i = 0; i < size / 2; i++) { for (int j = 0; j < size; j++) { swapInSpace(mat, i, j, size - (i + 1), j); } } }这里是Java的版本： 1234567891011121314public static void rightRotate(int[][] matrix, int n) { for (int layer = 0; layer < n / 2; layer++) { int first = layer; int last = n - 1 - first; for (int i = first; i < last; i++) { int offset = i - first; int temp = matrix[first][i]; matrix[first][i] = matrix[last-offset][first]; matrix[last-offset][first] = matrix[last][last-offset]; matrix[last][last-offset] = matrix[i][last]; matrix[i][last] = temp; } } }该方法的第一rotate mostouter层，然后移动到的内在的squentially层。 C代码将[N，M]二维数组向右旋转90度 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace MatrixProject { // mattrix class class Matrix{ private int rows; private int cols; private int[,] matrix; public Matrix(int n){ this.rows = n; this.cols = n; this.matrix = new int[this.rows,this.cols]; } public Matrix(int n,int m){ this.rows = n; this.cols = m; this.matrix = new int[this.rows,this.cols]; } public void Show() { for (var i = 0; i < this.rows; i++) { for (var j = 0; j < this.cols; j++) { Console.Write("{0,3}", this.matrix[i, j]); } Console.WriteLine(); } } public void ReadElements() { for (var i = 0; i < this.rows; i++) for (var j = 0; j < this.cols; j++) { Console.Write("element[{0},{1}]=",i,j); this.matrix[i, j] = Convert.ToInt32(Console.ReadLine()); } } // rotate [n,m] 2D array by 90 deg right public void Rotate90DegRight() { // create a mirror of current matrix int[,] mirror = this.matrix; // create a new matrix this.matrix = new int[this.cols, this.rows]; for (int i = 0; i < this.rows; i++) { for (int j = 0; j < this.cols; j++) { this.matrix[j, this.rows - i - 1] = mirror[i, j]; } } // replace cols count with rows count int tmp = this.rows; this.rows = this.cols; this.cols = tmp; } } class Program { static void Main(string[] args) { Matrix myMatrix = new Matrix(3,4); Console.WriteLine("Enter matrix elements:"); myMatrix.ReadElements(); Console.WriteLine("Matrix elements are:"); myMatrix.Show(); myMatrix.Rotate90DegRight(); Console.WriteLine("Matrix rotated at 90 deg are:"); myMatrix.Show(); Console.ReadLine(); } } }结果： 12345678910111213141516171819202122 Enter matrix elements: element[0,0]=1 element[0,1]=2 element[0,2]=3 element[0,3]=4 element[1,0]=5 element[1,1]=6 element[1,2]=7 element[1,3]=8 element[2,0]=9 element[2,1]=10 element[2,2]=11 element[2,3]=12 Matrix elements are: 1 2 3 4 5 6 7 8 9 10 11 12 Matrix rotated at 90 deg are: 9 5 1 10 6 2 11 7 3 12 8 4# transpose是一个标准的Ruby的阵列方法的类，因此： 12345% irb irb(main):001:0> m = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 0, 1, 2], [3, 4, 5, 6]] => [[1, 2, 3, 4], [5, 6, 7, 8], [9, 0, 1, 2], [3, 4, 5, 6]] irb(main):002:0> m.reverse.transpose => [[3, 9, 5, 1], [4, 0, 6, 2], [5, 1, 7, 3], [6, 2, 8, 4]]的实施是一个N ^ 2 transposition函数写在这里：你可以看到它。 HTTP:/ / www.ruby-doc.org /核心/方法- 1.9.3 array.html # I transpose 选择"由大toggle点击"源"beside transpose"。 我记得比O(N ^ 2)的解决方案，但只为specially建成矩阵(如sparse矩阵) 这里是我的attempt为90随便啦，窦或这是一个旋转矩阵的两个步骤的解决方案在第一transpose C.在地方swap然后的矩阵的列。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#define ROWS 5 #define COLS 5 void print_matrix_b(int B[][COLS], int rows, int cols) { for (int i = 0; i |
| CopyRight 2018-2019 实验室设备网 版权所有 |